class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        for (int i = 0; i < s.size(); ++i) {
            char ch = s[i];
            if (ch == ')' || ch == ']' || ch == '}') {
                if (st.empty() || (st.top() + 1 != ch && st.top() + 2 != ch)) return false;
                st.pop();
            } else {
                st.push(ch);
            }
        }

        return st.size() == 0;
    }
};